﻿#include "stdafx.h"
#include "GenerateParenthesis.h"

using namespace std;

namespace algorithm {

    void CGenerateParenthesis::RecurseGenerate(stack<int>& cache, bool bLeft, int left, int right, string& str, vector<string>& vec)
    {
        if (bLeft) {
            cache.push(0);
            left--;
            str.append("(");
        }
        else {
            if (cache.empty()) {
                return;//括号不匹配，错误；（剪枝）
            }
            else {
                cache.pop();
                str.append(")");
                right--;
            }
        }

        if (left == 0 && right == 0) {
            vec.push_back(str);
            //printf("str = %s\n", str.c_str());
        }
        else if (left == 0) {
            RecurseGenerate(cache, false, left, right, str, vec);
        }
        else if (right == 0) {
            RecurseGenerate(cache, true, left, right, str, vec);
        }
        else {
            string old = str;
            stack<int> temp = cache;
            RecurseGenerate(cache, true, left, right, str, vec);
            str = old;
            cache = temp;
            RecurseGenerate(cache, false, left, right, str, vec);
        }
    }
    vector<string> CGenerateParenthesis::Generate(int n)
    {
        vector<string> vec;
        if (!n) {
            return vec;
        }
        int left = n;//左括号数
        int right = n;//右括号数
        stack<int> cache;

        string str;
        RecurseGenerate(cache, true, left, right, str, vec);

        return vec;
    }
}
